package org.example.myleet.divide;

public class DividingSolution {

    /**
     * 53【分治法】最大子数组和
     * 官方分治法解：https://leetcode.cn/problems/maximum-subarray/solutions/228009/zui-da-zi-xu-he-by-leetcode-solution/?envType=daily-question&envId=2023-11-20
     * 对于一个区间 [l,r]，我们可以维护四个量：
     * lSum 表示 [l,r] 内以 l 为左端点的最大子段和
     * rSum 表示 [l,r] 内以 r 为右端点的最大子段和
     * mSum 表示 [l,r] 内的最大子段和
     * iSum 表示 [l,r] 的区间和
     * 以下简称 [l,m] 为 [l,r] 的「左子区间」，[m+1,r] 为 [l,r] 的「右子区间」。我们考虑如何维护这些量呢（如何通过左右子区间的信息合并得到 [l,r] 的信息）？对于长度为 1 的区间 [i,i]，四个量的值都和 nums[i] 相等。对于长度大于 1 的区间：
     * 首先最好维护的是 iSum，区间 [l,r] 的 iSum 就等于「左子区间」的 iSum 加上「右子区间」的 iSum。
     * 对于 [l,r] 的 lSum，存在两种可能，它要么等于「左子区间」的 lSum，要么等于「左子区间」的 iSum 加上「右子区间」的 lSum，二者取大。
     * 对于 [l,r] 的 rSum，同理，它要么等于「右子区间」的 rSum，要么等于「右子区间」的 iSum 加上「左子区间」的 rSum，二者取大。
     * 当计算好上面的三个量之后，就很好计算 [l,r] 的 mSum 了。我们可以考虑 [l,r] 的 mSum 对应的区间是否跨越 m——它可能不跨越 m，也就是说 [l,r] 的 mSum 可能是「左子区间」的 mSum 和 「右子区间」的 mSum 中的一个；它也可能跨越 m，可能是「左子区间」的 rSum 和 「右子区间」的 lSum 求和。三者取大。
     * 这样问题就得到了解决。
     */
    static class SegmentStatus {
        //表示 [l,r] 内以 l 为左端点的最大子段和
        int lSum;
        //表示 [l,r] 内以 r 为右端点的最大子段和
        int rSum;
        //表示 [l,r] 内的最大子段和
        int mSum;
        //表示 [l,r] 的区间和
        int iSum;

        public SegmentStatus(int lSum, int rSum, int iSum, int mSum) {
            this.lSum = lSum;
            this.rSum = rSum;
            this.iSum = iSum;
            this.mSum = mSum;
        }
    }
    private SegmentStatus getInfo(int[] nums, int l, int r) {
        if (l == r) {
            return new SegmentStatus(nums[l], nums[r], nums[l], nums[l]);
        }
        int m = (l + r) >> 1;
        SegmentStatus lSeg = getInfo(nums, l, m);
        SegmentStatus rSeg = getInfo(nums, m + 1, r);
        int lSum = Math.max(lSeg.lSum, lSeg.iSum + rSeg.lSum);
        int rSum = Math.max(rSeg.rSum, rSeg.iSum + lSeg.rSum);
        int iSum = lSeg.iSum + rSeg.iSum;
        int mSum = Math.max(lSeg.rSum + rSeg.lSum, Math.max(rSeg.mSum, lSeg.mSum));
        return new SegmentStatus(lSum, rSum, iSum, mSum);
    }
    public int maxSubArray(int[] nums) {
        return getInfo(nums, 0, nums.length - 1).mSum;
    }

    /**
     * 307【分块处理】区域和检索 - 数组可修改
     */
    static class NumArray {
        //初始化的数组，后面更新也用到
        private int[] nums;
        //数组长度
        private int n;
        //分块每块求和结果快照
        private int[] sumArr;
        //每块大小（最后一块除外），sqrt(n)
        private int blockSize;
        //分块的块数
        private int len;

        public NumArray(int[] nums) {
            //时间复杂度O(n)
            //初始化各个变量
            this.nums = nums;
            n = nums.length;
            blockSize = (int) Math.sqrt(n);
            len = n / blockSize + ((n % blockSize) == 0 ? 0 : 1);
            sumArr = new int[len];
            //初始化每块的和的快照，注意最后一块的大小不一定是blocSize
            for (int i = 0; i < len; ++i) {
                int blockSum = 0;
                int start = i * blockSize;
                int end = i == (len - 1) ? n : ((i + 1) * blockSize);
                for (int j = start; j < end; ++j) {
                    blockSum += nums[j];
                }
                sumArr[i] = blockSum;
            }
        }

        public void update(int index, int val) {
            //时间复杂度O(sqrt(n))
            //更新index位置的值
            nums[index] = val;
            //找到index的块blockId，注意最后一块大小稍有不同
            int blockId = index / blockSize;
            int end = blockId == (len - 1) ? n : ((blockId + 1) * blockSize);
            //更新块的和的快照
            int blockSum = 0;
            for (int j = blockId * blockSize; j < end; ++j) {
                blockSum += nums[j];
            }
            sumArr[blockId] = blockSum;
        }

        public int sumRange(int left, int right) {
            int answer = 0;
            for (int i = 0; i < len; ++i) {
                //每一个块都遍历一次，对于被left和right覆盖到的块进行求和，时间复杂度O(sqrt(n))
                int start = i * blockSize;
                int end = i == (len - 1) ? n : ((i + 1) * blockSize);
                //块没有在left和right区域内
                if (right < start || end <= left) continue;
                //如果块被left和right完整覆盖，则直接取快照结果
                if (left <= start && right >= end - 1) {
                    answer += sumArr[i];
                    continue;
                }
                //在块里寻找这部分数字的和
                if (start < left) {
                    start = left;
                }
                if (right < end - 1) {
                    end = right + 1;
                }
                for (int j = start; j < end; ++j) {
                    answer += nums[j];
                }
            }
            return answer;
        }
    }
}
